// https://leetcode.cn/problems/distinct-subsequences-ii/
// Created by ade on 2022/10/14.
// 给定一个字符串 s，计算 s 的 不同非空子序列 的个数。因为结果可能很大，所以返回答案需要对 10^9 + 7 取余 。
//
//字符串的 子序列 是经由原字符串删除一些（也可能不删除）字符但不改变剩余字符相对位置的一个新字符串。
//
//例如，"ace" 是 "abcde" 的一个子序列，但 "aec" 不是。
#include <iostream>
#include <string>
#include <map>
#include <vector>


using namespace std;

class Solution {
public:
    // 参考：https://leetcode.cn/problems/distinct-subsequences-ii/solution/bu-tong-by-capital-worker-vga3/
    int distinctSubseqII(string s) {
        int MOD = 1e9 + 7;
        vector<int> prev(26);
        int currentCount = 1;
        for (int i = 0; i < s.size(); i++) {
            int newCount = currentCount;
            currentCount = ((currentCount + newCount) % MOD - prev[s[i] - 'a'] % MOD + MOD) % MOD;
            prev[s[i] - 'a'] = newCount;
        }

        return currentCount - 1;
    }
};